package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/5/1 6:48
 **/
public class HouseRobberII213 {
    public static void main(String[] args) {
        new HouseRobberII213().rob1(new int[]{6,6,4,8,4,3,3,10});
    }

    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }


    public int rob1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        if(length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        if(length == 3) {
            return Math.max(Math.max(nums[0], nums[1]), nums[2]);
        }

        int first = dp(nums,  0,length-2);
        int second = dp(nums, 1, length-1);
        return Math.max(first, second);
    }

    private  int dp(int[] nums, int start,  int length) {
//        int[] dp = new int[length+1];
//        dp[0] = nums[start];
//        dp[1] = Math.max(nums[start], nums[start+1]);
        int first = nums[start];
        int second = Math.max(first, nums[start + 1]);
        for (int i = start+2; i <= length; i++) {
            // 打i-2和i 与打i-1比
//            dp[i-1] = Math.max(dp[i - start - 2] + nums[i], dp[i - start - 1]);
            int temp = second;
            second = Math.max(second, nums[i] + first);
            first = second;
        }
//        return dp[length];
        return second;
    }
}
